
#define _BSD_SOURCE
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <errno.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

#include "config.h"

#include "zbd-cache.h"
#include "log.h"
#include "hashtable.h"

#include "../algorithms-general.h"

/* zbd-cache.h */
struct cache_page;
extern struct zbd_zone *zones_collection;
extern struct cache_runtime cache_rt;

extern int RMW(uint32_t zoneId, uint64_t from_blk, uint64_t to_blk);

/* most-specified objs */
struct page_payload
{
    uint64_t checked_round; // Abort 弃用
};

static uint64_t global_evic_round;

/* cache out */
static int eigreedy_get_zone_out();
static int compareByReleaseForMiss(const void *a, const void *b);
static int checkInMissHashTable(struct hash_table *hashtb, uint64_t tg_blk);

struct zoneFutureStat
{
    uint32_t zoneId;
    uint32_t releaseCnt;
    uint32_t willHits;
    uint32_t releaseForMiss;
    struct zoneFutureStat *pre, *next;
};

struct zfsIndex
{
    struct zoneFutureStat *zfs;
};

struct zoneFutureStat *zfsArray;
struct zfsIndex *zfsIdx;
uint64_t *TraceMAP;


static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target);


int eigreedy_init()
{
    /* init page priv field. */
    struct cache_page *page = cache_rt.pages;
    for (uint64_t i = 0; i < STT.n_cache_pages; page++, i++)
    {
        page->priv = calloc(1, sizeof(struct page_payload));
        if (!page->priv)
            return -1;
    }

    global_evic_round = 0;

    zfsArray = (struct zoneFutureStat *)malloc(sizeof(struct zoneFutureStat) * N_ZONES);
    if (!zfsArray)
    {
        exit(EXIT_FAILURE);
    };

    zfsIdx = (struct zfsIndex *)malloc(sizeof(struct zfsIndex) * N_ZONES);
    if (!zfsIdx)
    {
        exit(EXIT_FAILURE);
    };

    char tracemap[128];
    sprintf(tracemap, "%s_%d", config_trace_seq_mmap_file_prefix, STT.traceId);
    int maxMapReq = 2000000000;
    
    int tracemapfd = open(tracemap, O_RDONLY);
    if (tracemapfd < 0)
    {
        // open trace file
        
        if ((tracemapfd = open(tracemap, O_RDWR | O_CREAT)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
        ftruncate(tracemapfd, sizeof(uint64_t) * maxMapReq);

        TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ | PROT_WRITE, MAP_SHARED, tracemapfd, 0);
        if (TraceMAP == (void *)-1)
        {
            log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }

        FILE *trace = fopen(TRACE_FILES[STT.traceId], "rt");
        if (trace == NULL)
        {
            exit(EXIT_FAILURE);
        };

        char action;
        uint64_t tg_blk;
        int mask;
        uint64_t *wrtReq = TraceMAP;
        uint64_t scanReqCnt = 0;
        while (!feof(trace)) // && scanReqCnt < STT.presetReq)
        {
            int ret;
#ifdef TRACE_SYSTOR17
            ret = fscanf(trace, "%c %d %lu\n", &action, &mask, &tg_blk);
#else
            ret = fscanf(trace, "%d %d %lu\n", &action, &mask, &tg_blk);
#endif

            if (ret < 0)
            {
                log_err_sac("error while reading trace file.");
                break;
            }

#ifdef TRACE_SYSTOR17
            tg_blk /= BLKSIZE;
#endif
            tg_blk += STT.start_Blkoff;

            if (action == ACT_WRITE && (STT.workload_mode & 0x02))
            {
                if ((tg_blk / N_ZONEBLK) > N_ZONES)
                {
                    log_info_sac("[warning] func:%s, target block overflow. \n", __func__);
                    continue;
                }

                *wrtReq = tg_blk;
                wrtReq++;
                scanReqCnt++;
            }
        }

        fclose(trace);
        msync(TraceMAP, sizeof(uint64_t) * maxMapReq, MS_SYNC);
        munmap(TraceMAP, sizeof(uint64_t) * maxMapReq);
        close(tracemapfd);
        // reopen
        if ((tracemapfd = open(tracemap, O_RDONLY)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
    }

    TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ, MAP_SHARED, tracemapfd, 0);
    if (TraceMAP == (void *)-1)
    {
        log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }
    return 0;
}

int eigreedy_login(struct cache_page *page, int op)
{
    // struct page_payload * p = (struct page_payload *)page->priv;
    // p->checked_round = 0;
    return 0;
}

int eigreedy_logout(struct cache_page *page, int op)
{
    return 0;
}

int eigreedy_hit(struct cache_page *page, int op)
{
    return 0;
}

int eigreedy_writeback_privi(int type)
{
    int ret, cnt = 0;
    struct page_payload *payload;

    if (type == FOR_READ)
        goto EVICT_CLEAN;
    else if (type == FOR_WRITE || type == FOR_UNKNOWN)
        goto EVICT_DIRTY;
    else
    {
        log_err_sac("[%s] error: MOST cache algorithm needs to be told eviction page type. \n", __func__);
        exit(EXIT_FAILURE);
    }

EVICT_CLEAN:
    log_err_sac("This offline algorithm doesn't support evicting clean block.");
    exit(EXIT_FAILURE);

EVICT_DIRTY:
    global_evic_round++;
    ret = eigreedy_get_zone_out();
    return ret;
}

static int eigreedy_get_zone_out()
{
    int best_zoneId = -1;
    uint32_t from = 0, to = N_ZONEBLK - 1;

    struct zbd_zone *z = zones_collection;
    // Traverse every zone.
    for (int i = 0; i < N_ZONES; i++)
    {
        struct zbd_zone *z = zones_collection + i;
        struct zoneFutureStat *zfs = zfsArray + i;

        zfs->zoneId = z->zoneId;
        zfs->releaseCnt = z->cblks_wtr;
        zfs->willHits = 0;
        zfs->releaseForMiss = z->cblks_wtr;
    }
    qsort(zfsArray, N_ZONES, sizeof(struct zoneFutureStat), compareByReleaseForMiss);


    // for(int i = 0; i < N_ZONES ; i++){
    //     struct zoneFutureStat * zfs = zfsArray + i;
    //     if(zfs->releaseForMiss == 0)
    //         break;
    //     printf("[%d]: zid=%d, cblk=%d\t ", i, zfs->zoneId, zfs->releaseCnt );
    // }
    // printf("\n");

    struct zoneFutureStat *zfs = zfsArray;
    zfs->pre = NULL;
    struct zoneFutureStat *prezfs = zfs;
    struct zfsIndex *idx;
    idx = zfsIdx + zfs->zoneId;
    idx->zfs = zfs;

    int i = 1;
    while (i < N_ZONES)
    {
        zfs = zfsArray + i;

        zfs->pre = prezfs;
        prezfs->next = zfs;
        prezfs = zfs;

        idx = zfsIdx + zfs->zoneId;
        idx->zfs = zfs;
        i++;
    }
    zfs->next = NULL;

    uint32_t round_misses = 0;
    struct zoneFutureStat *zfs_header = zfsArray;

    uint64_t *wrtTgtBlk = TraceMAP + STT.resetReqSeq + STT.reqcnt_w;
    if (*wrtTgtBlk != STT.curTargetBlk)
    {
        log_err_sac("[%s] offline algorithm is inconsistent with workload. \n", __func__);
        exit(EXIT_FAILURE);
    }
    uint64_t canWalkTo = STT.resetReqSeq + STT.reqcnt_w;

    struct hash_table *incomePageHashTable;
    HashTab_crt(STT.n_cache_pages, &incomePageHashTable);

    while (round_misses <= zfs_header->releaseForMiss && canWalkTo < STT.presetReq)
    {
        //log_info_sac("\ncheck hashtb: tgblk=%ld --> ", *wrtTgtBlk);
        if (checkInMissHashTable(incomePageHashTable, *wrtTgtBlk))
        {
            //log_info_sac("hit in level 1.");
            // Distinct block
            wrtTgtBlk++;
            canWalkTo++;
            continue;
        }

        struct cache_page *hitPage = CheckHit(*wrtTgtBlk);
        if (hitPage == NULL)
        {   
            //log_info_sac("missed in all levels.");
            round_misses++;
            HashTab_Insert(incomePageHashTable, *wrtTgtBlk, canWalkTo);

            uint32_t belong_zoneId = *wrtTgtBlk / N_ZONEBLK;

            if(belong_zoneId == 2296){
                int kk = 1;
            }
            
            struct zfsIndex *idx = zfsIdx + belong_zoneId;
            zfs = idx->zfs;
            if(zfs->releaseCnt >0){
                zfs->releaseForMiss ++;
                
                if (zfs->pre != NULL && zfs->releaseForMiss > zfs->pre->releaseForMiss)
                {
                    struct zoneFutureStat *insert_zfs = zfs;
                    while (insert_zfs->pre != NULL && zfs->releaseForMiss > insert_zfs->pre->releaseForMiss)
                    {
                        insert_zfs = insert_zfs->pre;
                    }

                    zfs_insertfront(zfs, insert_zfs);
                    if(zfs_header->pre == zfs){
                        zfs_header = zfs;
                    }
                }
            }
        }
        else
        {
            //log_info_sac("hit in level 0.");
            // hit in zone
            // struct page_payload* p = hitPage->priv;
            // if(p->checked_round == global_evic_round){
            //     // this round has been checked this page
            //     break;
            // }
            struct zfsIndex *idx = zfsIdx + hitPage->belong_zoneId;
            zfs = idx->zfs;
            zfs->willHits++;
        }

        wrtTgtBlk++;
        canWalkTo++;
    }
    HashTab_free(incomePageHashTable);

    best_zoneId = zfs_header->zoneId;

    // output write amplification.
    z = zones_collection + best_zoneId;
    uint32_t rmw_scope = N_ZONEBLK - from;
    double wa = (double)rmw_scope / z->cblks_wtr;

    log_info_sac("[%s] Zone[%d] WA: %.2f (%u/%u); walkstep: %ld \n", __func__, z->zoneId, wa, rmw_scope, z->cblks_wtr, canWalkTo - STT.resetReqSeq - STT.reqcnt_w);

    // RMW
    RMW(best_zoneId, from, to);

    return best_zoneId;
}

static int compareByReleaseForMiss(const void *a, const void *b) //用来做比较的函数。
{
    return ((struct zoneFutureStat *)a)->releaseForMiss < ((struct zoneFutureStat *)b)->releaseForMiss;
}

static int checkInMissHashTable(struct hash_table *hashtb, uint64_t tg_blk)
{
    if (HashTab_Lookup(hashtb, tg_blk, NULL) < 0)
        return 0;
    return 1;
}

static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target){
    if(target == NULL || zfs == NULL)
        return;

    if(target == zfs){
        return;
    }

    // take off zfs
    if(zfs->pre != NULL){ zfs->pre->next = zfs->next; }
    if(zfs->next != NULL) { zfs->next->pre = zfs->pre; }

    // insert in front of the target. 

    zfs->pre = target->pre;
    zfs->next = target;
    if (target->pre != NULL)
    {
        target->pre->next = zfs;
    }
    target->pre = zfs;
}